Implementacija grafova 
Vrsta: Seminarski | Broj strana: 17 | Nivo: Visoka poslovna škola strukovnih studija, Blac

Graf G je par skupova (V,E) gde je V konačan neprazan skup, a skup E predstavlja binarne relacije elemenata skupa V.
Elementi skupa V se nazivaju čvorovi, a elementi skupa E grane. Broj elemenata skupa V se naziva red grafa. U realnim problemima, čvorovi predstavljaju objekte, a grane odnose između njih.
Svakoj grani x iz skupa E odgovara samo jedan par čvorova (u,v), iz V koje ona spaja. Za granu x se kaze da je incidentna čvorovima u i v. svaki čvor međutim ne mora da ima incidentnu granu.
Ako se parovi čvorova (u,v) koji odgovaraju granama uređeni, radi se o usmeremom grafu ili digrafu, a ako su ovi parovi neuređeni radi se o neusmerenom grafu.
Ako u grafu ima i usmerenih i neusmerenih grana radi se o mešovitom grafu.
U usmerenom grafu grane su usmerene, stoga za dati čvor incidentne grane mogu biti ulazne ili izlazne.
Čvorovi (n i v) koji odgovaraju jednoj grani u neusmerenom grafu su međusobno susedni, jer je (u,v) jednako (v,u).
Kod usmerenog grafa, samo je čvor V susedan čvoru u, jer relacija susednosti nije simetrična.
Ukupan broj incidentnih grana određuje stepen čvora. U slucaju usmerenog grafa mogu se posebno definisati izlazni stepen i ulazni stepen. Ukupni stepen je jednak zbiru ulaza i izlaza stepena. Grana tipa (u,v) koje počinju i završavaju na istom čvoru nazivaju se petljama i njihov čvor nije bitan.
Čvorovi grafa su obično numerisani ili označeni imenima.
Ukoliko su granama grafa pridružene težine w(u,v) on se naziva težinskim grafom. Ponekad se usmereni težinski graf naziva mrežom.
Ako su čvorovi na putu različiti, osim eventualno prvog i poslednjeg tj. ako put ne prelazi više od jednom kroz isti čvor, radi se o prostom putu. Ciklus u grafu je prost put koji počinje i završava se u istom čvoru. Graf je cikličan ako sadrži bar jedan ciklus, a graf bez ciklusa se naziva acikličnim grafom. Usmeren acikličan graf se naziva dag (direct acyclic graph).
Neusmeren graf kod kojeg su svaka dva čvor susedna naziva se kompletnim grafom. Neusmeren graf je povezan ako između svaka dva čvora postoji put. U suprotnom se graf sastoji iz vise od jedne povezane komponente (maksimalno povezanog podgrafa).
Za razliku od predhodno definisanih stabala, koji se još nazivaju i korenim stablima, postoji pojam i slobodnih stabala, kod kojih ni jedan čvor nema svojih korena.

---------- CEO RAD MOŽETE PREUZETI NA SAJTU. ---------- 

www.maturski.org 

 

MOŽETE NAS KONTAKTIRATI NA E-MAIL: [email protected]